/*
https://leetcode-cn.com/problems/soup-servings/solution/fen-tang-by-leetcode/
 */
public class Solution808 {
    public double soupServings(int n) {
        n=(n/25)+(n%25==0?0:1);
        if (n>=1000){
            return 1;
        }
        double[][] f=new double[n+1][n+1];
        for (int i=0;i<=n;i++){
            for (int j=0;j<=n;j++){
                if (i==0 && j==0){
                    f[i][j]=0.5;
                }else if (i==0){
                    f[i][j]=1;
                }else if (j==0){
                    f[i][j]=0;
                }else {
                    f[i][j]=0.25*(f[Math.max(0,i-4)][j]+f[Math.max(0,i-3)][Math.max(0,j-1)]+f[Math.max(0,i-2)][Math.max(0,j-2)]+f[Math.max(0,i-1)][Math.max(0,j-3)]);
                }
            }
        }
        return f[n][n];
    }

    public static void main(String[] args) {
        System.out.println(new Solution808().soupServings(100));
    }
}
